#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <vector>
#include <set>
#include <string>

using namespace std;

const unsigned int ASCII_A = 97;
const unsigned int ASCII_Z = ASCII_A + 26;

typedef size_t                            etat_t;
typedef unsigned char                     symb_t;
typedef set< etat_t >                     etatset_t;
typedef vector< vector< etatset_t > >     trans_t;
typedef vector< etatset_t >               epsilon_t;

/*!
 * \brief Répresente un automate finit non deterministe avec epsilon transition
 */
struct sAutoNDE{
    /*!
     * \brief nb_etats Nombre d'état
     */
    size_t nb_etats;
    /*!
     * \brief nb_symbs Nombre de symboles acceptés
     */
    size_t nb_symbs;
    /*!
     * \brief nb_finaux Nombre d'états finaux
     */
    size_t nb_finaux;
    /*!
     * \brief initial Numéro de l'état initial
     */
    etat_t initial;
    /*!
     * \brief finaux Ensemble de numéro des états finaux
     */
    etatset_t finaux;
    /*!
     * \brief trans Matrice de transition qui pour chaque etat et chaque symbole associe un ensemble d'état de destination
     */
    trans_t trans;
    /*!
     * \brief epsilon Matrice de transitions spontanées qui pour chaque état associe un ensemble d'état de destination accéssible par epsilon transition
     */
    epsilon_t epsilon;
};

void Warshall(sAutoNDE &at);

/*!
 * \brief FromFile lit le fichier en entré et remplit la structure automate avec les informations luent.
 * \param at automate à renseigner
 * \param path chemin du fichier contenant la description de l'automate
 * \return TRUE si la lecture s'est bien passée, FALSE sinon
 */
bool FromFile(sAutoNDE& at, string path){
    ifstream myfile(path.c_str(), ios::in);
    //un flux d'entree obtenu à partir du nom du fichier
    string line;
    // un ligne lue dans le fichier avec getline(myfile,line);
    istringstream iss;
    // flux associé à la chaine, pour lire morceau par morceau avec >> (comme cin)
    etat_t s(0), t(0);
    // deux états temporaires
    symb_t a(0);
    // un symbole temporaire

    if (myfile.is_open()){
        // la première ligne donne 'nb_etats nb_symbs nb_finaux'
        do{
            getline(myfile,line);
        } while (line.empty() || line[0]=='#');
        // on autorise les lignes de commentaires : celles qui commencent par '#'
        iss.str(line);
        if((iss >> at.nb_etats).fail() || (iss >> at.nb_symbs).fail() || (iss >> at.nb_finaux).fail())
            return false;
        // la deuxième ligne donne l'état initial
        do{
            getline (myfile,line);
        } while (line.empty() || line[0]=='#');
        iss.clear();
        iss.str(line);
        if((iss >> at.initial).fail())
            return -1;

        // les autres lignes donnent les états finaux
        for(size_t i = 0; i < at.nb_finaux; i++){
            do{
                getline (myfile,line);
            } while (line.empty() || line[0]=='#');
            iss.clear();
            iss.str(line);
            if((iss >> s).fail())
                continue;
            at.finaux.insert(s); //remplir finaux
            cerr << "s= " << s << endl;
        }

        // on alloue les vectors à la taille connue à l'avance pour éviter les resize dynamiques
        at.trans.resize(at.nb_symbs);
        for(size_t i=0;i<at.nb_symbs;++i)
            at.trans[i].resize(at.nb_etats);
        at.epsilon.resize(at.nb_etats);
        // lecture de la relation de transition
        while(myfile.good()){
            line.clear();
            getline (myfile,line);
            if (line.empty() && line[0]=='#')
                continue;
            iss.clear();
            iss.str(line);

            // si une des trois lectures echoue, on passe à la suite
            if((iss >> s).fail() || (iss >> a).fail() || (iss >> t).fail() || (a< ASCII_A ) || (a> ASCII_Z ))
                continue;

            //test espilon ou non
            if ((a-ASCII_A) >= at.nb_symbs) {
                cerr << "s=" << s<< ", (e), t=" << t << endl;
                at.epsilon[s].insert(t); //remplit epsilon
            }
            else {
                cerr << "s=" << s<< ", a=" << a-ASCII_A << ", t=" << t << endl;
                at.trans[a-ASCII_A][s].insert(t); //remplit trans
            }
        }
        myfile.close();
        Warshall(at);
        return true;
    }
    return false;
    // on ne peut pas ouvrir le fichier
}

/*!
 * \brief ContientFinal Teste si l'ensemble des état passé en argument contient au moins un état final
 * \param at automate
 * \param e ensemble d'état final
 * \return VRAI si l'ensemble des état passé en argument contient au moins un état final, FALSE sinon
 */
bool ContientFinal(const sAutoNDE& at,const etatset_t& e){
    set<etat_t>::const_iterator first1 = at.finaux.begin();
    set<etat_t>::const_iterator last1 = at.finaux.end();
    set<etat_t>::const_iterator first2 = e.begin();
    set<etat_t>::const_iterator last2 = e.end();
    while ((first1!=last1) && (first2!=last2))
    {
        if (*first1<*first2)
            first1++;
        else{
            if (*first2<*first1)
                first2++;
            else
                return true;
        }
    }
    return false;
}

/*!
 * \brief Fermeture Calcul la fermeture transitive des état accessible par epsilon transition à partir de l'ensemble d'états passés en arguments
 * \param at automate
 * \param e ensemble d'état à clores en entrée-sortie
 */
void Fermeture(const sAutoNDE& at, etatset_t& e)
{
    // Cette fonction clot l'ensemble d'états E={e_0, e_1, ... ,e_n} passé en
    // paramètre avec les epsilon transitions
    etatset_t temp;
    for (etatset_t::const_iterator i = e.begin(); i != e.end(); i++)
    {
        temp.insert((*i));
        for(etatset_t::const_iterator j = at.epsilon[(*i)].begin(); j != at.epsilon[(*i)].end(); j++)
        {
            temp.insert(*j);
        }
    }
    e = temp;
}

/*!
 * \brief EstDeterministe Test si l'automate passé en argument est déterministe.
 * \param at automate
 * \return VRAI si l'automate est déterministe, FALSE sinon
 */
bool EstDeterministe(const sAutoNDE& at){
    for(epsilon_t::const_iterator it = at.epsilon.begin(); it != at.epsilon.end(); it++)
    {
        if ((*it).size() != 0)
        {
            return false;
        }
    }
    for (trans_t::const_iterator i = at.trans.begin(); i != at.trans.end(); i++)
    {
        for (vector<etatset_t>::const_iterator j = (*i).begin(); j != (*i).end(); j++)
        {
            if((*j).size() > 1)
            {
                return false;
            }
        }
    }
    return true;
}

/*!
 * \brief Warshall Calcul pour chaque état de l'automate passé en argument la fermeture transitive des états accéssible par epsilone transition
 * \param at automate
 * \note Utilise l'algorithme de Warshall qui néssécite en premier lieux une convertion de la matrice de transition
 *vers un graphe de relation binaire modélisé par un tableau à deux dimension de booléens.
 */
void Warshall(sAutoNDE& at)
{
    //Cette fonction aurai très bien put être créée par Chuck Norris
    const unsigned int n = at.nb_etats;
    bool** C = new bool*[n];
    bool** A = new bool*[n];

    //On ninitialise les matrices d'adjacence à false. C'est a dire que toute les relation binaire entre état sont a FAUX.
    for (unsigned int i = 0; i < n; i++) {
        C[i] = new bool[n];
        A[i] = new bool[n];
        for (unsigned int j = 0; j < n; j++) {
            C[i][j] = false;
            A[i][j] = false;
        }
    }

    //On crée un compteur pour connaitre la position de notre itérateur dans la première boucle
    int count = 0;
    //On parcours tout les état de départ de notre tableau d'epsilon transition
    for(epsilon_t::const_iterator i = at.epsilon.begin(); i != at.epsilon.end(); i++) {
        //Pour chaque état de départ, on parcours les différents états de destination de l'espilone transition
        for (etatset_t::const_iterator j = (*i).begin(); j != (*i).end(); j++) {
            //On remplit l'état de la relation binaire de notre matrice d'adjacence comme étant VRAI
            //Nous avons donc l'index de notre état de départ qui correspond à la variable count
            //L'index de notre état de destination qui correspond à la variable (*j)
            //On définie donc la relation binaire entre l'état de départ et destination à VRAI
            //Ce qui signifie que se chemin existe.
            C[count][(unsigned int)(*j)] = true;
        }
        count++;
    }

    unsigned int i, j, k;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            A[i][j] = C[i][j];
    for(k = 0; k < n; k++)
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                A[i][j] = A[i][j] || (A[i][k] && A[k][j]);

    count = 0;
    //Pour chaque état de départ
    for(epsilon_t::const_iterator i = at.epsilon.begin(); i != at.epsilon.end(); i++) {
        //Pour chaque relaction binaire depuis cet état de départ
        //Ce qui reviens a tester tout les état de destination
        for (j = 0; j < n; j++) {
            //Si la relation existe entre cet état de départ et cet état de destination.
            if(A[count][j]) {
                at.epsilon[count].insert(j); //On insert le numéro d'état dans notre ensemble de destination. (peu importe s'il existe déjà).
            }
        }
        count++;
    }
}

/*!
 * \brief Delta Cette fonction prend un automate, un ensemble d'état E={e_0, e_1, ... ,e_n}
     et renvoie l'ensemble des états accessibles depuis au moins un des e_i.
     Autrement dit, c'est l'union des ensembles d'états x_i tels que x_i = {x | (e_i,c,x) in Delta}
 * \param at automate
 * \param e ensemble d'états
 * \param c symbole à lire par l'automate de type unsigned char
 * \return
 */
etatset_t Delta(const sAutoNDE& at, const etatset_t& e, symb_t c){
    etatset_t res;

    etatset_t temp = e;
    Fermeture(at,temp);
    for (etatset_t::const_iterator i = temp.begin(); i != temp.end(); i++)
    {
        for (etatset_t::const_iterator j = at.trans[c-97][(*i)].begin(); j != at.trans[c-97][(*i)].end(); j++)
        {
            res.insert(*j);
        }
    }
    return res;
}

/*!
 * \brief Accept Cette fonction prend en argument un automate et détermine si il accepte le mot str
 * \param at automate
 * \param str chaine de caractère de type string à lire par l'automate
 * \return VRAI si la chaine de caractère passé en argument est acceptée par l'automate, FAUX sinon
 */
bool Accept(const sAutoNDE& at, string str){
    etatset_t res;
    res.insert(at.initial);
    for(string::const_iterator it = str.begin(); it != str.end(); it++)
    {
        res = Delta(at, res, *it);
    }
    Fermeture(at,res);
    if(ContientFinal(at,res))
        return true;
    return false;
}

/*!
 * \brief main Fonction principale
 */
int main( int argc, char* argv[] ){
    string path, str;
    bool r;
    sAutoNDE at;

    cout << "***TP LIF 15 ***" << endl;

    if(argc > 1)
        path.assign(argv[1]);
    else
        path = "./exempleNDE.txt";

    if(argc > 2)
        str.assign(argv[2]);
    else
        str = "abb";

    if (!FromFile(at, path)){
        cerr << "Erreur de lecture du fichier " << path << endl;
    }else{
        cerr << "Automate déterministe ? " << (EstDeterministe(at) ? "Vrai" : "Faux") << endl;
        r = Accept(at, str);
        cout << "'" << str  <<  "' est accepté ? " << (r ? "Vrai" : "Faux") << endl;
    }
    
    return EXIT_SUCCESS;
}
